import java.util.Set;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网:CC12 拆分词句
 * <a href="https://www.nowcoder.com/practice/5f3b7bf611764c8ba7868f3ed40d6b2c?tpId=46&tqId=29041&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking">...</a>
 * User: DELL
 * Data: 2023-03-16
 * Time: 23:51
 */
//题目分析
//状态定义:   F(i):s的前i个字符能否被分割成一个单词序列,且这些单词全部在dict中
//转移方程:   F(i) == true 当且仅当存在F(j) == true(0<=j<i) 且 substring[j,i]可以在dict中被找到
//状态初始化: F(0) = true
//返回结果:   F(s.length())
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s.length() == 0) {
            return false;
        }
        int len = s.length();
        boolean[] F = new boolean[len+1];
        F[0] = true;
        for (int i = 1; i < len+1; i++) {
            for (int j = 0; j < i; j++) {
                if (F[j] && dict.contains(s.substring(j,i))) {
                    F[i] = true;
                    break;
                }
            }
        }
        return F[len];
    }
}